home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 February: Tool Chest / Apple Developer CD Series Tool Chest February 1996 (Apple Computer)(1996).iso / Sample Code / AOCE Sample Code / PowerTalk Access Modules / Sample SMSAM / SampleSMSAM Source / TupleDatabase / RamTupleDatabase.cp < prev    next >
Encoding:
Text File  |  1995-07-28  |  8.7 KB  |  423 lines  |  [TEXT/MPS ]

  1. /*
  2.     File:        RamTupleDatabase.cp
  3.  
  4.     Copyright:    © 1991-1994 by Apple Computer, Inc.
  5.                 All rights reserved.
  6.  
  7.     Part of the AOCE Sample SMSAM Package.  Consult the license
  8.     which came with this software for your specific legal rights.
  9.  
  10. */
  11.  
  12.  
  13.  
  14. #ifndef __RAMTUPLEDATABASE__
  15. #include "RamTupleDatabase.h"
  16. #endif
  17.  
  18. #ifndef    __DEBUGASSERT__
  19. #include "DebugAssert.h"
  20. #endif
  21.  
  22. #ifndef    __DEBUGGINGGEAR__
  23. #include "DebuggingGear.h"
  24. #endif
  25.  
  26. #ifndef    __DEBUGCONSTANTS__
  27. #include "DebugConstants.h"
  28. #endif
  29.  
  30. #ifndef    __DIRECTOBJECT__
  31. #include "DirectObject.h"
  32. #endif
  33.  
  34. #pragma segment ATupleDatabase
  35.  
  36. class TDebugFlag;
  37. extern TDebugFlag chrisFlag;
  38.  
  39. /***********************************|****************************************/
  40.  
  41. class CTupleEntry : public TDirectObject
  42. {
  43. public:        CTupleEntry ( const ATupleKey& key, const ADataItem& data, CTupleEntry* parent = nil );
  44.     virtual    ~CTupleEntry ();
  45.  
  46.     virtual    ostream&                operator >> ( ostream& s ) const;
  47.  
  48. private:    CTupleEntry ( const CTupleEntry& );
  49.             CTupleEntry&            operator = ( const CTupleEntry& );
  50.  
  51.             CTupleEntry*            fParent;
  52.             CTupleEntry*            fLeft;
  53.             CTupleEntry*            fRight;
  54.             unsigned long            fIndex;
  55.             CTupleKey                fKey;
  56.             CDataItem                fData;
  57.  
  58.     friend class TRamTupleDatabase;
  59. };
  60.  
  61. /***********************************|****************************************/
  62.  
  63. CTupleEntry::CTupleEntry ( const ATupleKey& key, const ADataItem& data, CTupleEntry* parent ):
  64.     fParent ( parent ),
  65.     fLeft ( nil ),
  66.     fRight ( nil ),
  67.     fIndex ( 0 ),
  68.     fKey ( key ),
  69.     fData ( data )
  70. {
  71. }
  72.  
  73. /***********************************|****************************************/
  74.  
  75. CTupleEntry::~CTupleEntry ()
  76. {
  77.     delete fLeft;
  78.     delete fRight;
  79. }
  80.  
  81. /***********************************|****************************************/
  82.  
  83. ostream&
  84. CTupleEntry::operator >> ( ostream& s ) const
  85. {
  86.     #if 1
  87.     return s << "CTupleEntry: " << fKey << " " << fData << endl;
  88.     #else
  89.     s << "CTupleEntry @ " << (void*) this << '\n';
  90.     s << "\tfParent: " << (void*) fParent << '\n';
  91.     s << "\tfLeft: " << (void*) fLeft << '\n';
  92.     s << "\tfRight: " << (void*) fRight << '\n';
  93.     s << "\tfKey: " << fKey << '\n';
  94.     s << "\tfData: " << fData << '\n';
  95.     return s << "\tfIndex: " << fIndex << '\n';
  96.     #endif
  97. }
  98.  
  99. /***********************************|****************************************/
  100. /***********************************|****************************************/
  101.  
  102. TRamTupleDatabase::TRamTupleDatabase ():
  103.     ATupleDatabase (),
  104.     fRoot ( nil ),
  105.     fTupleCount ( 0 )
  106. {
  107. }
  108.  
  109. /***********************************|****************************************/
  110.  
  111. TRamTupleDatabase::~TRamTupleDatabase ()
  112. {
  113.     delete fRoot;
  114. }
  115.  
  116. /***********************************|****************************************/
  117.  
  118. CTupleEntry*
  119. TRamTupleDatabase::FindTuple ( const ATupleKey& key ) const
  120. {
  121.     CTupleEntry* tuple = fRoot;
  122.  
  123.     while ( tuple )
  124.     {
  125.         long relation = key.Compare ( tuple->fKey );
  126.  
  127.         if ( relation > 0 )
  128.             tuple = tuple->fRight;
  129.         else if ( relation < 0 )
  130.             tuple = tuple->fLeft;
  131.         else
  132.             return tuple;
  133.     }
  134.  
  135.     return tuple;
  136. }
  137.  
  138. /***********************************|****************************************/
  139.  
  140. CTupleEntry*&
  141. TRamTupleDatabase::FindTuple ( const ATupleKey& key, CTupleEntry*& parent ) const
  142. {
  143.     parent = nil;
  144.     CTupleEntry** tuple = (CTupleEntry**) &fRoot; // whoa-- this can't be right?pfl
  145.  
  146.     while ( *tuple )
  147.     {
  148.         long relation = key.Compare ( (*tuple)->fKey );
  149.  
  150.         if ( relation > 0 )
  151.         {
  152.             parent = *tuple;
  153.             tuple = &(*tuple)->fRight;
  154.         }
  155.         else if ( relation < 0 )
  156.         {
  157.             parent = *tuple;
  158.             tuple = &(*tuple)->fLeft;
  159.         }
  160.         else
  161.         {
  162.             break;
  163.         }
  164.     }
  165.  
  166.     return *tuple;
  167. }
  168.  
  169. /***********************************|****************************************/
  170.  
  171. Boolean
  172. TRamTupleDatabase::SetTuple ( const ATupleKey& key, const ADataItem& data )
  173. {
  174.     CTupleEntry* parent;
  175.     CTupleEntry*& tuple = FindTuple ( key, parent );
  176.  
  177.     if ( tuple )
  178.     {
  179.         tuple->fData = data;
  180.     }
  181.     else
  182.     {
  183.         tuple = new CTupleEntry ( key, data, parent );
  184.  
  185.         if ( tuple )
  186.         {
  187.             tuple->fIndex = ++fTupleCount;
  188.         }
  189.     }
  190.  
  191.     return tuple != nil;
  192. }
  193.  
  194. /***********************************|****************************************/
  195.  
  196. Boolean
  197. TRamTupleDatabase::GetTupleDataSize ( const ATupleKey& key, unsigned long& dataSize )
  198. {
  199.     const CTupleEntry* tuple = FindTuple ( key );
  200.  
  201.     if ( tuple )
  202.     {
  203.         dataSize = tuple->fData.GetPhysicalLength ();
  204.         return true;
  205.     }
  206.  
  207.     return false;
  208. }
  209.  
  210. /***********************************|****************************************/
  211.  
  212. Boolean
  213. TRamTupleDatabase::GetTupleData ( unsigned long index, ADataItem& data )
  214. {
  215.     const CTupleEntry* tuple = FindTuple ( index, fRoot );
  216.  
  217.     if ( tuple )
  218.     {
  219.         data = tuple->fData;
  220.         return true;
  221.     }
  222.  
  223.     return false;
  224. }
  225.  
  226. /***********************************|****************************************/
  227.  
  228. Boolean
  229. TRamTupleDatabase::GetTupleData ( const ATupleKey& key, ADataItem& data )
  230. {
  231.     const CTupleEntry* tuple = FindTuple ( key );
  232.  
  233.     if ( tuple )
  234.     {
  235.         data = tuple->fData;
  236.         return true;
  237.     }
  238.  
  239.     return false;
  240. }
  241.  
  242. /***********************************|****************************************/
  243.  
  244. Boolean
  245. TRamTupleDatabase::DoesTupleExist ( const ATupleKey& key ) const
  246. {
  247.     return FindTuple ( key ) != nil;
  248. }
  249.  
  250. /***********************************|****************************************/
  251.  
  252. Boolean
  253. TRamTupleDatabase::DeleteTuple ( const ATupleKey& key )
  254. {
  255.     CTupleEntry* tuple = FindTuple ( key );
  256.  
  257.     if ( tuple )
  258.     {
  259.         // the scheme for deleting this node involves attaching our
  260.         // right child subtree to our parent, and finding the node
  261.         // to which our left child subtree should be attached to.
  262.  
  263.         CTupleEntry* parent = tuple->fParent;
  264.  
  265.         if ( parent )
  266.         {
  267.             // something is not right; our parent does not think we are its child
  268.             ASSERT_RETURN_ZERO ( parent->fRight == tuple || parent->fLeft == tuple );
  269.  
  270.             CTupleEntry* leftSubtree = tuple->fLeft;
  271.             CTupleEntry* rightSubtree = tuple->fRight;
  272.  
  273.             if ( parent->fLeft == tuple )
  274.                 parent->fLeft = rightSubtree;
  275.             else if ( parent->fRight == tuple )
  276.                 parent->fRight = rightSubtree;
  277.  
  278.             if ( leftSubtree )
  279.             {
  280.                 CTupleEntry*& leftAttach = FindTuple ( leftSubtree->fKey, parent );
  281.  
  282.                 // theoretically we should always be reattaching our left
  283.                 // subtree to a nil leaf node pointer in some other node
  284.                 ASSERT_RETURN_ZERO ( leftAttach == nil );
  285.  
  286.                 leftAttach = leftSubtree;
  287.             }
  288.         }
  289.  
  290.         tuple->fLeft = nil;        // nil these out so the delete does not propogate
  291.         tuple->fRight = nil;    // nil these out so the delete does not propogate
  292.         delete tuple;
  293.         fTupleCount--;
  294.         return true;
  295.     }
  296.  
  297.     return false;
  298. }
  299.  
  300. /***********************************|****************************************/
  301.  
  302. unsigned long
  303. TRamTupleDatabase::CountTuples () const
  304. {
  305.     return fTupleCount;
  306. }
  307.  
  308. /***********************************|****************************************/
  309.  
  310. Boolean
  311. TRamTupleDatabase::GetTuple ( unsigned long index, ATupleKey& key, ADataItem& data )
  312. {
  313.     const CTupleEntry* tuple = FindTuple ( index, fRoot );
  314.  
  315.     if ( tuple )
  316.     {
  317.         key = tuple->fKey;
  318.         data = tuple->fData;
  319.         return true;
  320.     }
  321.  
  322.     return false;
  323. }
  324.  
  325. /***********************************|****************************************/
  326.  
  327. CTupleEntry*
  328. TRamTupleDatabase::FindTuple ( unsigned long index, CTupleEntry* tuple ) const
  329. {
  330.     if ( tuple )
  331.     {
  332.         if ( tuple->fIndex == index )
  333.             return tuple;
  334.  
  335.         CTupleEntry* right = FindTuple ( index, tuple->fLeft );
  336.  
  337.         if ( right )
  338.             return right;
  339.  
  340.         return FindTuple ( index, tuple->fRight );
  341.     }
  342.  
  343.     return tuple;
  344. }
  345.  
  346. /***********************************|****************************************/
  347.  
  348. Boolean
  349. TRamTupleDatabase::GetTupleKey ( unsigned long index, ATupleKey& key )
  350. {
  351.     const CTupleEntry* tuple = FindTuple ( index, fRoot );
  352.  
  353.     if ( tuple )
  354.     {
  355.         key = tuple->fKey;
  356.         return true;
  357.     }
  358.  
  359.     return false;
  360. }
  361.  
  362. /***********************************|****************************************/
  363.  
  364. Boolean
  365. TRamTupleDatabase::FindIndexOfTuple ( const ATupleKey& key, unsigned long& index ) const
  366. {
  367.     CTupleEntry* entry = FindTuple ( key );
  368.  
  369.     if ( entry )
  370.     {
  371.         index = entry->fIndex;
  372.         return true;
  373.     }
  374.  
  375.     return false;
  376. }
  377.  
  378. /***********************************|****************************************/
  379.  
  380. Boolean
  381. TRamTupleDatabase::SetTuple ( unsigned long index, const ADataItem& data )
  382. {
  383.     CTupleEntry* tuple = FindTuple ( index, fRoot );
  384.  
  385.     if ( tuple )
  386.     {
  387.         tuple->fData = data;
  388.         return true;
  389.     }
  390.  
  391.     return false;
  392. }
  393.  
  394. /***********************************|****************************************/
  395.  
  396. void
  397. TRamTupleDatabase::PrintSubtree ( ostream& s, const CTupleEntry* e ) const
  398. {
  399.     if ( e )
  400.     {
  401.         PrintSubtree ( s, e->fLeft );
  402.         s << e << '\n';
  403.         PrintSubtree ( s, e->fRight );
  404.     }
  405. }
  406.  
  407. /***********************************|****************************************/
  408.  
  409. ostream&
  410. TRamTupleDatabase::operator >> ( ostream& s ) const
  411. {
  412.     s << "TRamTupleDatabase @ " << (void*) this << '\n';
  413.     s << "\tfTupleCount: " << fTupleCount << '\n';
  414.     s << "\tfRoot: " << (void*) fRoot << '\n';
  415.  
  416.     if ( chrisFlag.Flag ( kExtensiveTupleDBDescribe ) )
  417.         PrintSubtree ( s, fRoot );
  418.  
  419.     return s;
  420. }
  421.  
  422. /***********************************|****************************************/
  423.